import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-07-22
 * Time: 22:48
 */
public class test_2 {
    public int longestArithSeqLength(int[] nums) {
        // 优化
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(nums[0], 0);

        // 建表
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) // 初始化
            Arrays.fill(dp[i], 2);

        int ret = 2;
        for (int i = 1; i < n; i++) // 固定倒数第⼆个数
        {
            for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
            {
                int a = 2 * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }

    public int numberOfArithmeticSlices(int[] nums) {
        // 优化
        Map<Long, List<Integer>> hash = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            long tmp = (long) nums[i];
            if (!hash.containsKey(tmp))
                hash.put(tmp, new ArrayList<Integer>());
            hash.get(tmp).add(i);
        }
        int[][] dp = new int[n][n];
        int sum = 0;
        for (int j = 2; j < n; j++) // 固定倒数第⼀个数
            for (int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                long a = 2L * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    for (int k : hash.get(a))
                        if (k < i) dp[i][j] += dp[k][i] + 1;
                        else break; // ⼩优化
                }
                sum += dp[i][j];
            }
        return sum;
    }
    public int countSubstrings(String s)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int ret = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i; j < n; j++)
            {
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if(dp[i][j])
                    ret++;
            }
        }
        return ret;
    }


    public String longestPalindrome(String s)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int begin = 0, len = 1; // 标记⼀下最⻓⼦串的起始位置和⻓度
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = i; j < n; j++)
            {
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if(dp[i][j] && j - i + 1 > len)
                {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + len);
    }
    public boolean checkPartitioning(String s)
    {
        // 1. 利⽤ dp 处理⼀下所有的⼦串是否回⽂
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--)
            for(int j = i; j < n; j++)
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;

        // 2. 枚举第⼆个字符串所有的起始位置和终⽌位置
        for(int i = 1; i < n - 1; i++)
            for(int j = i; j < n - 1; j++)
                if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
        return false;
    }
    public int minCut(String s)
    {
        // 1. 预处理
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--)
            for(int j = i; j < n; j++)
                if(s.charAt(i) == s.charAt(j))
                    isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;

        int[] dp = new int[n];
        for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++)
        {
            if(isPal[0][i]) dp[i] = 0;
            else
            {
                for(int j = 1; j <= i; j++)
                    if(isPal[j][i])
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n - 1];
    }
}
